package class03;

import java.util.ArrayList;

public class Code01_ReverseList {

    //单链表
    public static class Node{
        public int value;
        public Node next;

        public Node(int data){
            value=data;
        }
    }

    //双链表
    public static class DoubleNode{
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data){
            value=data;
        }
    }

    //反转单链表
    public static Node reverseLinkedList(Node head){
        Node pre=null;
        Node next=null;

        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

    //反转双链表
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre=null;
        DoubleNode next=null;

        while(head!=null){
            next=head.next;
            head.next=pre;
            head.last=next;
            pre=head;
            head=next;
        }
        return pre;
    }

    //测试单链表
    public static Node testReverseLinkedList(Node head){
        ArrayList<Node> list=new ArrayList<>();
        while(head!=null){
            list.add(head);
            head=head.next;
        }
        list.get(0).next=null;
        //获取链表的节点数量
        int N=list.size();
        for (int i = 1; i <N ; i++) {
            list.get(i).next=list.get(i-1);
        }
        return list.get(N-1);
    }

    //测试双链表
    public static DoubleNode testReverseDoubleList(DoubleNode head){
        if (head==null){
            return null;
        }
        ArrayList<DoubleNode> list=new ArrayList<>();
        while (head!=null){
            list.add(head);
            head=head.next;
        }
        list.get(0).next=null;
        DoubleNode pre=list.get(0);
        int N=list.size();
        for (int i = 1; i <N ; i++) {
            DoubleNode cur=list.get(i);
            cur.last=null;
            cur.next=pre;
            pre.last=cur;
            pre=cur;
        }
        return list.get(N-1);
    }
}

